{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Expression Add Operators"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: addOperators"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #给表达式添加运算符"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个仅包含数字&nbsp;<code>0-9</code>&nbsp;的字符串 <code>num</code> 和一个目标值整数 <code>target</code> ，在 <code>num</code> 的数字之间添加 <strong>二元 </strong>运算符（不是一元）<code>+</code>、<code>-</code>&nbsp;或&nbsp;<code>*</code>&nbsp;，返回 <strong>所有</strong> 能够得到 <code>target </code>的表达式。</p>\n",
    "\n",
    "<p>注意，返回表达式中的操作数 <strong>不应该</strong> 包含前导零。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <code>num = </code>\"123\", target = 6\n",
    "<strong>输出: </strong>[\"1+2+3\", \"1*2*3\"] \n",
    "<strong>解释: </strong>“1*2*3” 和 “1+2+3” 的值都是6。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <code>num = </code>\"232\", target = 8\n",
    "<strong>输出: </strong>[\"2*3+2\", \"2+3*2\"]\n",
    "<strong>解释:</strong> “2*3+2” 和 “2+3*2” 的值都是8。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <code>num = </code>\"3456237490\", target = 9191\n",
    "<strong>输出: </strong>[]\n",
    "<strong>解释: </strong>表达式 “3456237490” 无法得到 9191 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num.length &lt;= 10</code></li>\n",
    "\t<li><code>num</code> 仅含数字</li>\n",
    "\t<li><code>-2<sup>31</sup> &lt;= target &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [expression-add-operators](https://leetcode.cn/problems/expression-add-operators/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [expression-add-operators](https://leetcode.cn/problems/expression-add-operators/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"123\"\\n6', '\"232\"\\n8', '\"3456237490\"\\n9191']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def addOperators(self, num: str, target: int) -> List[str]:\n",
    "#         l = list(num)\n",
    "#         n = len(num)\n",
    "#         build = list(\"x\".join(l)) \n",
    "#         result = []\n",
    "#         def recurse(d, sign, val, prev, is_mul):\n",
    "#             new_mul = 0\n",
    "#             build[2*d+1] = sign\n",
    "#             if sign == '+':\n",
    "#                 new_prev = int(build[2*d+2])\n",
    "#                 new_val = val + new_prev\n",
    "#             if sign == '-':\n",
    "#                 new_prev = -int(build[2*d+2])\n",
    "#                 new_val = val + new_prev\n",
    "#             if sign == '*':\n",
    "#                 new_prev = prev*int(build[2*d+2])\n",
    "#                 new_val = val - prev + new_prev\n",
    "#                 new_mul = int(build[2*d+2])\n",
    "#             if sign == '':\n",
    "#                 if is_mul:\n",
    "#                     new_mul = is_mul*10 - int(build[2*d+2]) if is_mul<0 else is_mul*10 + int(build[2*d+2])\n",
    "#                     new_prev = prev // is_mul * new_mul\n",
    "#                     new_val = val - prev + new_prev\n",
    "#                 else:\n",
    "#                     new_prev = prev*10 - int(build[2*d+2]) if prev<0 else prev*10 + int(build[2*d+2])\n",
    "#                     new_val = val - prev + new_prev\n",
    "#             if d == n-2:\n",
    "#                 if new_val == target:\n",
    "#                     result.append(\"\".join(build))\n",
    "#             else:\n",
    "#                 recurse(d+1, \"+\", new_val, new_prev,new_mul)\n",
    "#                 recurse(d+1, \"-\", new_val, new_prev,new_mul)\n",
    "#                 recurse(d+1, \"*\", new_val, new_prev,new_mul)\n",
    "#                 if build[2*d+2] != \"0\" or build[2*d+1] == \"\":\n",
    "#                     recurse(d+1,\"\", new_val, new_prev,new_mul)\n",
    "#             build[2*d+1] = 'x'\n",
    "#         for sign in [\"+\",\"-\",\"*\"]:\n",
    "#             recurse(0,sign,int(build[0]),int(build[0]),0)\n",
    "#         if build[0]!=\"0\":\n",
    "#             recurse(0,\"\",int(build[0]),int(build[0]),0)\n",
    "#         return result\n",
    "        \n",
    "        \n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        build = list(\"x\".join(list(num))) \n",
    "        result = []\n",
    "        def recurse(d, val, prev, is_mul):\n",
    "            if d == n-1:\n",
    "                if val == target:\n",
    "                    result.append(\"\".join(build))\n",
    "                return\n",
    "            next_digit = int(build[2*d+2])\n",
    "            build[2*d+1] = \"+\"\n",
    "            recurse(d+1, val + next_digit, next_digit,0)\n",
    "            build[2*d+1] = \"-\"\n",
    "            recurse(d+1, val - next_digit, -next_digit,0)\n",
    "            build[2*d+1] = \"*\"\n",
    "            recurse(d+1, val - prev + prev*next_digit, prev*next_digit,next_digit)\n",
    "            if build[2*d] != \"0\" or build[2*d-1] == \"\":\n",
    "                # print(build[2*d] != \"0\", build[2*d-1] == \"\")\n",
    "                build[2*d+1] = \"\"\n",
    "                if is_mul:\n",
    "                    new_mul = is_mul*10 - next_digit if is_mul<0 else is_mul*10 + next_digit\n",
    "                    recurse(d+1, val - prev + prev // is_mul * new_mul, prev // is_mul * new_mul, new_mul)\n",
    "                else:\n",
    "                    new_prev = prev*10 - next_digit if prev<0 else prev*10 + next_digit\n",
    "                    recurse(d+1, val - prev + new_prev, new_prev, 0)\n",
    "        recurse(0,int(build[0]),int(build[0]),0)\n",
    "        return result\n",
    "        \n",
    "# class Solution:\n",
    "#     def addOperators(self, num: 'str', target: 'int') -> 'List[str]':\n",
    "\n",
    "#         N = len(num)\n",
    "#         answers = []\n",
    "#         def recurse(index, prev_operand, current_operand, value, string):\n",
    "\n",
    "#             # Done processing all the digits in num\n",
    "#             if index == N:\n",
    "\n",
    "#                 # If the final value == target expected AND\n",
    "#                 # no operand is left unprocessed\n",
    "#                 if value == target and current_operand == 0:\n",
    "#                     answers.append(\"\".join(string[:]))\n",
    "#                 return\n",
    "\n",
    "#             # Extending the current operand by one digit\n",
    "#             current_operand = current_operand*10 + int(num[index])\n",
    "#             str_op = str(current_operand)\n",
    "\n",
    "#             # To avoid cases where we have 1 + 05 or 1 * 05 since 05 won't be a\n",
    "#             # valid operand. Hence this check\n",
    "#             if current_operand > 0:\n",
    "\n",
    "#                 # NO OP recursion\n",
    "#                 recurse(index + 1, prev_operand, current_operand, value, string)\n",
    "\n",
    "#             # ADDITION\n",
    "#             string.append('+'); string.append(str_op)\n",
    "#             recurse(index + 1, current_operand, 0, value + current_operand, string)\n",
    "#             string.pop();string.pop()\n",
    "\n",
    "#             # SUBTRACTION\n",
    "#             string.append('-'); string.append(str_op)\n",
    "#             recurse(index + 1, -current_operand, 0, value - current_operand, string)\n",
    "#             string.pop();string.pop()\n",
    "\n",
    "#             # MULTIPLICATION\n",
    "#             string.append('*'); string.append(str_op)\n",
    "#             recurse(index + 1, current_operand * prev_operand, 0, value - prev_operand + (current_operand * prev_operand), string)\n",
    "#             string.pop();string.pop()\n",
    "#         recurse(1, int(num[0]), 0, int(num[0]), [num[0]])    \n",
    "#         return answers\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        def back(idx, sum_, pre):\n",
    "            nonlocal res\n",
    "            nonlocal path\n",
    "            if idx == n:\n",
    "                if sum_ == target:\n",
    "                    res.append(path[:])\n",
    "                return\n",
    "            pn = len(path)\n",
    "            for i in range(idx, n):\n",
    "                x_str = num[idx : i + 1]\n",
    "                x = int(x_str)\n",
    "                if idx == 0:\n",
    "                    path += x_str\n",
    "                    back(i + 1, sum_ + x, x)\n",
    "                    path = path[:pn]\n",
    "                else:\n",
    "                    path += '+' + x_str\n",
    "                    back(i + 1, sum_ + x, x)\n",
    "                    path = path[:pn]\n",
    "\n",
    "                    path += '-' + x_str\n",
    "                    back(i + 1, sum_ - x, -x)\n",
    "                    path = path[:pn]\n",
    "\n",
    "                    path += '*' + x_str\n",
    "                    back(i + 1, sum_ - pre + pre * x, pre * x)\n",
    "                    path = path[:pn]\n",
    "                \n",
    "                if x == 0:\n",
    "                    return\n",
    "        res = []\n",
    "        path = ''\n",
    "        n = len(num)\n",
    "        back(0, 0, 0)\n",
    "        return res\n",
    "                     \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        res = []\n",
    "\n",
    "        def backtrack(i, path, cur, prev):\n",
    "            if i>=len(num):\n",
    "                if cur == target:\n",
    "                    res.append(path)\n",
    "            else:\n",
    "                for j in range(i, len(num)):\n",
    "                    if j>i and num[i] == '0':\n",
    "                        break\n",
    "                    \n",
    "                    v = int(num[i:j+1])\n",
    "                    if i == 0:\n",
    "                        backtrack(j+1, str(v), v, v)\n",
    "                    else:\n",
    "                        backtrack(j+1, path+'+'+str(v), cur+v, v)\n",
    "                        backtrack(j+1, path+'-'+str(v), cur-v, -v)\n",
    "                        backtrack(j+1, path+'*'+str(v), cur-prev+prev*v, prev*v)\n",
    "\n",
    "        backtrack(0, '', 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        \n",
    "        ans = []\n",
    "        def backtrack(inx, expr, ret, mul):\n",
    "            if inx == n:\n",
    "                if ret == target:\n",
    "                    ans.append(expr)\n",
    "                return\n",
    "            \n",
    "            for i in range(1, n+1-inx):\n",
    "                if num[inx] == \"0\" and i > 1:break\n",
    "                val = int(num[inx:i + inx])\n",
    "                if inx == 0:\n",
    "                    backtrack(i, num[inx:i + inx], val, val)\n",
    "                else:\n",
    "                    backtrack(i + inx, expr+\"*\"+num[inx:i + inx], ret - mul + mul * val, mul*val)\n",
    "                    backtrack(i + inx, expr+\"+\"+num[inx:i + inx], ret+val, val)\n",
    "                    backtrack(i + inx, expr+\"-\"+num[inx:i + inx], ret-val, -val)\n",
    "        \n",
    "        backtrack(0, \"\", 0, 0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "\n",
    "        def backtrack(expr: List[str], i: int, res: int, mul: int):\n",
    "            if i == n:\n",
    "                if res == target:\n",
    "                    ans.append(''.join(expr))\n",
    "                return\n",
    "            signIndex = len(expr)\n",
    "            if i > 0:\n",
    "                expr.append('')  # 占位，下面填充符号\n",
    "            val = 0\n",
    "            for j in range(i, n):  # 枚举截取的数字长度（取多少位）\n",
    "                if j > i and num[i] == '0':  # 数字可以是单个 0 但不能有前导零\n",
    "                    break\n",
    "                val = val * 10 + int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i == 0:  # 表达式开头不能添加符号\n",
    "                    backtrack(expr, j + 1, val, val)\n",
    "                else:  # 枚举符号\n",
    "                    expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val)\n",
    "                    expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val)\n",
    "                    expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val)\n",
    "            del expr[signIndex:]\n",
    "\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\r\n",
    "        ans, n = [], len(num)\r\n",
    "        def f(idx, exp, pre, rst):\r\n",
    "            if idx == n:\r\n",
    "                if rst == target:\r\n",
    "                    ans.append(exp)\r\n",
    "                return \r\n",
    "            \r\n",
    "            for i in range(idx + 1, n + 1):\r\n",
    "                if num[idx] == '0' and i > idx + 1:\r\n",
    "                    break\r\n",
    "                val = int(num[idx:i])\r\n",
    "                if idx == 0:\r\n",
    "                    f(i, num[idx:i], val, val)\r\n",
    "                else:\r\n",
    "                    if int(num[idx:]) >= abs(target - rst):\r\n",
    "                        f(i, exp + '+' + num[idx:i], val, rst + val)\r\n",
    "                        f(i, exp + '-' + num[idx:i], -val, rst - val)\r\n",
    "                    f(i, exp + '*' + num[idx:i], pre * val, rst - pre + pre * val)\r\n",
    "        f(0, '', 0, 0)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\r\n",
    "        n = len(num)\r\n",
    "        ans = []\r\n",
    "\r\n",
    "        def backtrack(expr: List[str], i: int, res: int, mul: int):\r\n",
    "            if i == n:\r\n",
    "                if res == target:\r\n",
    "                    ans.append(''.join(expr))\r\n",
    "                return\r\n",
    "            signIndex = len(expr)\r\n",
    "            if i > 0:\r\n",
    "                expr.append('')  # 占位，下面填充符号\r\n",
    "            val = 0\r\n",
    "            for j in range(i, n):  # 枚举截取的数字长度（取多少位）\r\n",
    "                if j > i and num[i] == '0':  # 数字可以是单个 0 但不能有前导零\r\n",
    "                    break\r\n",
    "                val = val * 10 + int(num[j])\r\n",
    "                expr.append(num[j])\r\n",
    "                if i == 0:  # 表达式开头不能添加符号\r\n",
    "                    backtrack(expr, j + 1, val, val)\r\n",
    "                else:  # 枚举符号\r\n",
    "                    expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val)\r\n",
    "                    expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val)\r\n",
    "                    expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val)\r\n",
    "            del expr[signIndex:]\r\n",
    "\r\n",
    "        backtrack([], 0, 0, 0)\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "\n",
    "        def backtrack(expr: List[str], i: int, res: int, mul: int):\n",
    "            if i == n:\n",
    "                if res == target:\n",
    "                    ans.append(''.join(expr))\n",
    "                return\n",
    "            signIndex = len(expr)\n",
    "            if i > 0:\n",
    "                expr.append('')  # 占位，下面填充符号\n",
    "            val = 0\n",
    "            for j in range(i, n):  # 枚举截取的数字长度（取多少位）\n",
    "                if j > i and num[i] == '0':  # 数字可以是单个 0 但不能有前导零\n",
    "                    break\n",
    "                val = val * 10 + int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i == 0:  # 表达式开头不能添加符号\n",
    "                    backtrack(expr, j + 1, val, val)\n",
    "                else:  # 枚举符号\n",
    "                    expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val)\n",
    "                    expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val)\n",
    "                    expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val)\n",
    "            del expr[signIndex:]\n",
    "\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "\n",
    "        def backtrack(expr: List[str], i: int, res: int, mul: int):\n",
    "            if i == n:\n",
    "                if res == target:\n",
    "                    ans.append(''.join(expr))\n",
    "                return\n",
    "            signIndex = len(expr)\n",
    "            if i > 0:\n",
    "                expr.append('')  # 占位，下面填充符号\n",
    "            val = 0\n",
    "            for j in range(i, n):  # 枚举截取的数字长度（取多少位）\n",
    "                if j > i and num[i] == '0':  # 数字可以是单个 0 但不能有前导零\n",
    "                    break\n",
    "                val = val * 10 + int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i == 0:  # 表达式开头不能添加符号\n",
    "                    backtrack(expr, j + 1, val, val)\n",
    "                else:  # 枚举符号\n",
    "                    expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val)\n",
    "                    expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val)\n",
    "                    expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val)\n",
    "            del expr[signIndex:]\n",
    "\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        ln = len(num)\n",
    "        ans = []\n",
    "        def backtrace(expr:List[str],index:int,res:int,mul:int):\n",
    "            if index == ln:\n",
    "                if res == target:\n",
    "                    ans.append(''.join(expr))\n",
    "                return\n",
    "            len_expr = len(expr)\n",
    "            expr.append('')\n",
    "            value = 0\n",
    "            for next_index in range(index,ln):\n",
    "                if num[index] == \"0\" and next_index > index:\n",
    "                    break\n",
    "                value = value * 10 + int(num[next_index])\n",
    "                expr.append(num[next_index])\n",
    "                if index == 0:\n",
    "                    backtrace(expr,next_index+1,res+value,value)\n",
    "                    continue\n",
    "                expr[len_expr]=\"+\"\n",
    "                backtrace(expr,next_index+1,res+value,value)\n",
    "                expr[len_expr]=\"-\"\n",
    "                backtrace(expr,next_index+1,res-value,-value)\n",
    "                expr[len_expr]=\"*\"\n",
    "                backtrace(expr,next_index+1,res-mul+mul*value,mul*value)\n",
    "            del expr[len_expr:]\n",
    "        backtrace([],0,0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        res = []\n",
    "        for s in itertools.product(['+', '-', '*', ''], repeat=len(num)-1):\n",
    "            x = ''\n",
    "            for i, j in zip(num, list(s)): x += i+j\n",
    "            x += num[-1]\n",
    "            try:\n",
    "                if not x.startswith('00') and '+00' not in x and '-00' not in x and '*00' not in x and eval(x) == target: res.append(x)\n",
    "            except:\n",
    "                pass\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef addOperators(self, num: str, target: int) -> List[str]:\n",
    "\t\tn = len(num)\n",
    "\n",
    "\t\tdef dfs(start, prefix, value, prev):\n",
    "\t\t\tif start == n:\n",
    "\t\t\t\tif value == target:\n",
    "\t\t\t\t\tans.append(prefix)\n",
    "\t\t\t\treturn\n",
    "\t\t\tfor end in range(start, n): # [start, end] 是当前考虑的数字字符串\n",
    "\t\t\t\tstring = num[start:end + 1]\n",
    "\t\t\t\tnumber = int(string)\n",
    "\t\t\t\tif end > start and num[start] == '0': break # 不能以 0 开头 , 后面不用再试了\n",
    "\t\t\t\tif start == 0:\n",
    "\t\t\t\t\tdfs(end + 1, string, number, number)\n",
    "\t\t\t\telse: # 剪枝，后面的数字绝对值最大的是全部连着也就是num[start:]，若它的值都小于与目标的差值，\n",
    "\t\t\t\t\t# 则只能进行乘法计算，希望前面的数字和后面相乘后的值会大于两者差值\n",
    "\t\t\t\t\tif int(num[start:]) >= abs(target - value):\n",
    "\t\t\t\t\t\tdfs(end + 1, prefix + '+' + string, value + number, number)\n",
    "\t\t\t\t\t\tdfs(end + 1, prefix + '-' + string, value - number, -number)\n",
    "\t\t\t\t\tdfs(end + 1, prefix + '*' + string, value - prev + prev * number, prev * number)\n",
    "\n",
    "\t\tans = []\n",
    "\t\tdfs(0, '', 0, 0)\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        res = []\n",
    "        def dfs(index: int, cur: str, curNum: int) -> None:\n",
    "            if index == n: \n",
    "                if eval(cur) == target:\n",
    "                    res.append(cur)\n",
    "                return\n",
    "            for next in [\"\", \"+\", \"-\", \"*\"]:\n",
    "                if next == \"\":\n",
    "                    if curNum == 0: \n",
    "                        continue\n",
    "                    dfs(index + 1, cur + num[index], curNum * 10 + int(num[index]))\n",
    "                else:\n",
    "                    dfs(index + 1, cur + next + num[index], int(num[index]))\n",
    "        dfs(1, num[0], int(num[0]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.paths = []\n",
    "        self.path = []\n",
    "\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        self.path.clear()\n",
    "        self.paths.clear()\n",
    "        self.backtracking(num, target, 0, 0, 0)\n",
    "        return self.paths\n",
    "\n",
    "    def backtracking(self, num, target, res, mul, startindex):\n",
    "        if startindex == len(num):\n",
    "            if res == target:\n",
    "                self.paths.append(\"\".join(self.path[:]))\n",
    "            return\n",
    "        signindex = len(self.path)\n",
    "        if startindex > 0:\n",
    "            self.path.append('')\n",
    "        val = 0\n",
    "        for i in range(startindex, len(num)):\n",
    "            if i>startindex and num[startindex] == '0':\n",
    "                break\n",
    "            val = val * 10 + int(num[i])\n",
    "            self.path.append(num[i])\n",
    "            if startindex == 0:\n",
    "                self.backtracking(num, target, val, val, i+1)\n",
    "            else:\n",
    "                self.path[signindex] = \"+\"\n",
    "                self.backtracking(num, target, res+val, val, i+1)\n",
    "                self.path[signindex] = \"-\"\n",
    "                self.backtracking(num, target, res-val, -val, i+1)\n",
    "                self.path[signindex] = \"*\"\n",
    "                self.backtracking(num, target, res-mul+mul*val, mul*val, i+1)\n",
    "        del self.path[signindex:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        def dfs(num, target, pos, exp, prev, curr, ans):\n",
    "            if pos == len(num):\n",
    "                if curr == target:\n",
    "                    ans.append(exp)\n",
    "                return\n",
    "            for l in range(1, len(num)-pos+1):\n",
    "                t = num[pos:pos+l]\n",
    "                if t[0] == \"0\" and len(t) > 1:break\n",
    "                n = int(t)\n",
    "                if pos == 0:\n",
    "                    dfs(num, target, l, t, n, n, ans)\n",
    "                    continue\n",
    "                dfs(num, target, pos+l, exp+'+'+t, n, curr+n, ans)\n",
    "                dfs(num, target, pos+l, exp+'-'+t, -n, curr-n, ans)\n",
    "                dfs(num, target, pos+l, exp+'*'+t, prev*n, curr-prev + prev * n,ans)\n",
    "        ans = []\n",
    "        dfs(num, target, 0, \"\", 0 , 0, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "\n",
    "        def backtrack(expr: List[str], i: int, res: int, mul: int):\n",
    "            if i == n:\n",
    "                if res == target:\n",
    "                    ans.append(''.join(expr))\n",
    "                return\n",
    "            signIndex = len(expr)\n",
    "            if i > 0:\n",
    "                expr.append('')  # 占位，下面填充符号\n",
    "            val = 0\n",
    "            for j in range(i, n):  # 枚举截取的数字长度（取多少位）\n",
    "                if j > i and num[i] == '0':  # 数字可以是单个 0 但不能有前导零\n",
    "                    break\n",
    "                val = val * 10 + int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i == 0:  # 表达式开头不能添加符号\n",
    "                    backtrack(expr, j + 1, val, val)\n",
    "                else:  # 枚举符号\n",
    "                    expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val)\n",
    "                    expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val)\n",
    "                    expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val)\n",
    "            del expr[signIndex:]\n",
    "\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        nums = list(num)\n",
    "        ans = []\n",
    "        path = [0] * (len(nums) *2 -1)\n",
    "        t = 0\n",
    "        for i in range(len(nums)):  # 尝试0~i前缀作为第一部分\n",
    "            # print(i)\n",
    "            t = t * 10 + ord(nums[i]) - ord('0')\n",
    "            path[i] = nums[i]\n",
    "            self.process2(nums, target, i+1, path, i+1, 0, t, ans)\n",
    "            if t == 0:  # 0不能作为开头和后面的数形成新数\n",
    "                break\n",
    "        return ans\n",
    "\n",
    "    # nums 存放原始的数据\n",
    "    # target 最终要达成的数据目标\n",
    "    # index 对nums的索引\n",
    "    # path 之前做的决定，已经从左往右依次填写的字符在其中，可能含有'0'~'9' 与 * - +\n",
    "    # left 已经确认不会变的部分\n",
    "    # cur 当前可能会被的部分\n",
    "    def process2(self, nums, target, index, path, length, left, cur, ans):\n",
    "        if index == len(nums):\n",
    "            if left + cur == target:\n",
    "                ans.append(''.join(path[:length]))\n",
    "            return\n",
    "        t = 0\n",
    "        j = length + 1\n",
    "        for i in range(index, len(nums)):\n",
    "            # print(i)\n",
    "            t = t * 10 + ord(nums[i]) - ord('0')\n",
    "            path[length] = '+'\n",
    "            path[j] = str(t)\n",
    "            self.process2(nums, target, i+1, path, j+1, left+cur, t, ans)\n",
    "            path[length] = '-'\n",
    "            # path[-1] = t\n",
    "            self.process2(nums, target, i+1, path, j+1, left+cur, -t, ans)\n",
    "            path[length] = '*'\n",
    "            # path.append(t)\n",
    "            self.process2(nums, target, i+1, path, j+1, left, cur * t, ans)\n",
    "            if nums[index] == '0':  # 0开头的话，不能和后面拼接在一起，形成新的数\n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        res = []\n",
    "\n",
    "        def backtrack(i, path, cur, pre):\n",
    "            if i>=len(num):\n",
    "                if cur == target:\n",
    "                    res.append(path)\n",
    "            else:\n",
    "                for j in range(i, len(num)):\n",
    "                    if j>i and num[i] == '0':\n",
    "                        break\n",
    "\n",
    "                    v = int(num[i:j+1])\n",
    "                    if i == 0:\n",
    "                        backtrack(j+1, str(v), v, v)\n",
    "                    else:\n",
    "                        backtrack(j+1, path+'+'+str(v), cur+v, v)\n",
    "                        backtrack(j+1, path+'-'+str(v), cur-v, -v)\n",
    "                        backtrack(j+1, path+'*'+str(v), cur-pre+pre*v, pre*v)\n",
    "\n",
    "        backtrack(0, '', 0, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        curItems = []\n",
    "        results = []\n",
    "        ops = [\"+\", \"-\", \"*\"]\n",
    "        \n",
    "        def _backtrack(startIdx):\n",
    "            if startIdx == len(num):\n",
    "                tmpResult = ''.join(curItems)\n",
    "                if eval(tmpResult) == target:\n",
    "                    results.append(tmpResult)\n",
    "                return\n",
    "\n",
    "            for endIdx in range(startIdx, len(num)):\n",
    "                curNum = num[startIdx: endIdx + 1]\n",
    "                if curNum[0] == '0' and endIdx > startIdx:              # leading zero\n",
    "                    break\n",
    "                curItems.append(curNum)\n",
    "                if endIdx == len(num) - 1:                              # no op for last num\n",
    "                    _backtrack(endIdx + 1)\n",
    "                    curItems.pop()\n",
    "                    continue\n",
    "                for op in ops:\n",
    "                    curItems.append(op)\n",
    "                    _backtrack(endIdx + 1)\n",
    "                    curItems.pop()\n",
    "                curItems.pop()\n",
    "        \n",
    "        _backtrack(0)\n",
    "\n",
    "        return results\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        lt = len(num)\n",
    "        ans = []\n",
    "        def backtrace(pre_list,pos,remain,mul):\n",
    "            if pos ==lt:\n",
    "                if remain == 0:\n",
    "                    ans.append(\"\".join(pre_list))\n",
    "                return\n",
    "            # add num\n",
    "\n",
    "            len_p = len(pre_list)\n",
    "            pre_list.append(\"\")\n",
    "            cur_value = 0\n",
    "            for i in range(pos,lt):\n",
    "                if i>pos and cur_value==0:\n",
    "                    break\n",
    "                cur_value = cur_value*10 + int(num[i])\n",
    "                pre_list.append(str(cur_value))\n",
    "                if pos ==0:\n",
    "                    backtrace(pre_list,i+1,remain - cur_value,cur_value)\n",
    "                    pre_list.pop()\n",
    "                    continue\n",
    "                # op + \n",
    "                pre_list[len_p]=\"+\"\n",
    "                backtrace(pre_list,i+1,remain - cur_value,cur_value)\n",
    "                # op - \n",
    "                pre_list[len_p]=\"-\"\n",
    "                backtrace(pre_list,i+1,remain + cur_value,-cur_value)\n",
    "                # op * \n",
    "                pre_list[len_p]=\"*\"\n",
    "                backtrace(pre_list,i+1,remain - cur_value*mul + mul,cur_value*mul)\n",
    "                pre_list.pop() \n",
    "            del pre_list[len_p:]\n",
    "        backtrace([],0,target,0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "\n",
    "        def dfs(location, sub_str, ans=[]):\n",
    "             \n",
    "            if location == len(num):\n",
    "                try:\n",
    "                    if eval(sub_str) == target:\n",
    "                        ans.append(sub_str)\n",
    "                        return\n",
    "                    return\n",
    "                except:\n",
    "                    return \n",
    "            \n",
    "            for i in range(location+1, len(num)+1):\n",
    "                new_sub_str = num[location: i]\n",
    "                if new_sub_str != '0' and new_sub_str.startswith('0'):\n",
    "                    continue\n",
    "                if location != 0:\n",
    "                    for char in ['+', '-', '*']:\n",
    "                        dfs(i, sub_str + char + new_sub_str, ans)\n",
    "                else:\n",
    "                    dfs(i, new_sub_str, ans)\n",
    "        ans = []\n",
    "        dfs(0, '', ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        res = []\n",
    "        def dfs(index: int, prev: int, cur: int, ss: str) -> None:\n",
    "            if index == n:\n",
    "                if cur == target: res.append(ss)\n",
    "                return \n",
    "            for j in range(index, n):\n",
    "                if j != index and num[index] == '0': break \n",
    "                valStr = num[index : j + 1]\n",
    "                val = int(valStr)\n",
    "                if index == 0:\n",
    "                    dfs(j + 1, val, val, ss + valStr)\n",
    "                else:\n",
    "                    dfs(j + 1, val, cur + val, ss + \"+\" + valStr)\n",
    "                    dfs(j + 1, -val, cur - val, ss + \"-\" + valStr)\n",
    "                    x = prev * val \n",
    "                    dfs(j + 1, x, cur - prev + x, ss + \"*\" + valStr)\n",
    "        dfs(0, 0, 0, \"\")\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        multi, add, sub = \"*\", \"+\", \"-\"\n",
    "\n",
    "        ret = []\n",
    "        def backtrack(inx, expr):\n",
    "            if inx == n:\n",
    "                if eval(expr) == target:\n",
    "                    ret.append(expr)\n",
    "                return\n",
    "            \n",
    "            for i in range(1, n+1-inx):\n",
    "                if num[inx] == \"0\" and i > 1:break\n",
    "                if i == n - inx:\n",
    "                    backtrack(i + inx, expr+num[inx:i + inx])\n",
    "                    continue\n",
    "                for op in [multi, add, sub]:\n",
    "                    backtrack(i + inx, expr+num[inx:i + inx]+op)\n",
    "        backtrack(0, \"\")\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "\n",
    "        def dfs(expr, i, res, mul):\n",
    "            if i == n:\n",
    "                if res == target:\n",
    "                    ans.append(\"\".join(expr))\n",
    "                    return \n",
    "            sign_index = len(expr)\n",
    "            if i > 0:\n",
    "                expr.append('')\n",
    "            val = 0\n",
    "            for j in range(i, n):\n",
    "                if j > i and num[i] == '0':\n",
    "                    break\n",
    "                val = val * 10 + int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i == 0:\n",
    "                    dfs(expr, j + 1, val, val)\n",
    "                else:\n",
    "                    expr[sign_index] = '+'\n",
    "                    dfs(expr, j + 1, res + val, val)\n",
    "                    expr[sign_index] = '-'\n",
    "                    dfs(expr, j + 1, res - val, -val)\n",
    "                    expr[sign_index] = '*'\n",
    "                    dfs(expr, j + 1, res - mul + mul * val, mul * val)\n",
    "                \n",
    "            del expr[sign_index:]\n",
    "\n",
    "            \n",
    "        dfs([], 0, 0, 0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        res, n = [], len(num)\n",
    "        def dfs(s, i):\n",
    "            if i == n:\n",
    "                if eval(s) == target:\n",
    "                    res.append(s)\n",
    "                return\n",
    "            for ope in ['+', '-', '*']:\n",
    "                hi = i + 1 if num[i] == '0' else n\n",
    "                for j in range(i, hi):\n",
    "                    dfs(s + ope + num[i : j + 1], j + 1)\n",
    "        \n",
    "        hi = 1 if num[0] == '0' else n\n",
    "        for i in range(0, hi):\n",
    "            dfs(num[0: i + 1], i + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "\n",
    "        def backtrack(expr: List[str], i: int, res: int, mul: int):\n",
    "            if i == n:\n",
    "                if res == target:\n",
    "                    ans.append(''.join(expr))\n",
    "                return\n",
    "            signIndex = len(expr)\n",
    "            if i > 0:\n",
    "                expr.append('')  # 占位，下面填充符号\n",
    "            val = 0\n",
    "            for j in range(i, n):  # 枚举截取的数字长度（取多少位）\n",
    "                if j > i and num[i] == '0':  # 数字可以是单个 0 但不能有前导零\n",
    "                    break\n",
    "                val = val * 10 + int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i == 0:  # 表达式开头不能添加符号\n",
    "                    backtrack(expr, j + 1, val, val)\n",
    "                else:  # 枚举符号\n",
    "                    expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val)\n",
    "                    expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val)\n",
    "                    expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val)\n",
    "            del expr[signIndex:]\n",
    "\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n=len(num)\n",
    "        ans=[]\n",
    "        \n",
    "        def backtrack(expr,i,res,mul):\n",
    "            if i==n:\n",
    "                if res==target:\n",
    "                    ans.append(\"\".join(expr))\n",
    "                return\n",
    "            \n",
    "            signIndex=len(expr)\n",
    "            if i>0:\n",
    "                expr.append(\"\")\n",
    "            val=0\n",
    "            for j in range(i,n):\n",
    "                if j>i and num[i]==\"0\":\n",
    "                    break\n",
    "                val=val*10+int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i==0:\n",
    "                    backtrack(expr,j+1,val,val)\n",
    "                else:\n",
    "                    expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val)\n",
    "                    expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val)\n",
    "                    expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val)\n",
    "            del expr[signIndex:]\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        ret = []\n",
    "        path = []\n",
    "\n",
    "        def backtrack(start_index, res, mul):\n",
    "            # mul是最后一个连乘串的计算结果\n",
    "            if start_index == n:\n",
    "                if res == target:\n",
    "                    ret.append(\"\".join(path))\n",
    "                return\n",
    "            \n",
    "            sign_index = len(path)\n",
    "            # 运算符号占位\n",
    "\n",
    "            for i in range(start_index, n):\n",
    "                path.append(\"\")\n",
    "                # 数字可以是单个数字但不能有前导零\n",
    "                if i > start_index and num[start_index] == \"0\":\n",
    "                    path.pop()\n",
    "                    break\n",
    "                val = int(num[start_index:i+1])\n",
    "                path.append(num[start_index:i+1])\n",
    "                # 表达式开头不能添加符号\n",
    "                if start_index == 0:\n",
    "                    backtrack(i+1, val, val)\n",
    "                else:\n",
    "                    path[sign_index] = \"+\"\n",
    "                    backtrack(i+1, res + val, val)\n",
    "                    path[sign_index] = \"-\"\n",
    "                    backtrack(i+1, res - val, -val)\n",
    "                    path[sign_index] = \"*\"\n",
    "                    backtrack(i+1, res-mul+mul*val, mul*val)\n",
    "                path.pop()\n",
    "                path.pop()\n",
    "        backtrack(0, 0, 0)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculate(self, exp: str) -> int:\n",
    "        Res = 0\n",
    "        term = 1\n",
    "        num = 0\n",
    "        sign = 1\n",
    "        warning = False\n",
    "        for c in exp:\n",
    "            if c not in '+-*':\n",
    "                if warning: return None\n",
    "                if num or c != '0': num = 10*num + int(c)\n",
    "                else: warning = True\n",
    "            else:\n",
    "                term *= num\n",
    "                num = 0\n",
    "                warning = False\n",
    "                if c != '*':\n",
    "                    Res += sign * term\n",
    "                    term = 1\n",
    "                    sign = 2*int(c=='+')-1\n",
    "        term *= num\n",
    "        return Res + sign * term\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        #return self.calculate('34+0-04')\n",
    "        N = len(num)\n",
    "        Ans = []\n",
    "        for K in range(4**(N-1)):\n",
    "            exp = ''\n",
    "            for i in range(N):\n",
    "                exp = exp + num[i]\n",
    "                if K % 4 > 0: exp = exp + '*+-'[K%4-1]\n",
    "                K //= 4\n",
    "            if self.calculate(exp) == target: Ans.append(exp)\n",
    "        return Ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        res = []\n",
    "        n = len(num)\n",
    "        def dfs(i, exp, result, mult):\n",
    "            if i == n:\n",
    "                if result == target:\n",
    "                    res.append(''.join(exp))\n",
    "                return\n",
    "            val = 0\n",
    "            nxt = ''\n",
    "            for j in range(i, n):\n",
    "                if j > i and num[i] == '0':\n",
    "                    break\n",
    "                val = val * 10 + int(num[j])\n",
    "                nxt += num[j]\n",
    "                if i == 0:\n",
    "                    dfs(j+1, nxt, val, val)\n",
    "                else:\n",
    "                    dfs(j+1, exp+'+'+nxt, result+val, val)\n",
    "                    dfs(j+1, exp+'-'+nxt, result-val, -val)\n",
    "                    dfs(j+1, exp+'*'+nxt, result-mult+ mult*val, mult*val)\n",
    "        dfs(0, [], 0, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        res = []\n",
    "\n",
    "        def dfs(pre, head, i):\n",
    "            #print('pre ', pre, 'head', head, 'w',num[i])\n",
    "            if pre and pre[-1] in '+-*':\n",
    "                head = num[i]\n",
    "\n",
    "\n",
    "\n",
    "            pre += num[i]\n",
    "            if i == len(num) - 1:\n",
    "                if eval(pre) == target:\n",
    "                    res.append(pre[1:])\n",
    "                return\n",
    "\n",
    "            if head != '0':\n",
    "                dfs(pre, head, i + 1)\n",
    "            dfs(pre + '+', '', i + 1)\n",
    "            dfs(pre + '-', '', i + 1)\n",
    "            dfs(pre + '*', '', i + 1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        dfs('+', '', 0)\n",
    "        return sorted(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        res = []\n",
    "\n",
    "        def dfs(path, count, result, begin, prev):\n",
    "\n",
    "            if begin == n:\n",
    "                if result == target:\n",
    "                    res.append(path)\n",
    "                return\n",
    "            for i in range(begin, n):\n",
    "                if num[begin] == '0' and i != begin:\n",
    "                    break\n",
    "                next_num = int(num[begin:i+1])\n",
    "                if begin == 0:\n",
    "                    dfs(\"\"+num[begin:i+1], count + 1, next_num, i + 1, next_num)\n",
    "                else:\n",
    "                    dfs(path + \"+\" + num[begin:i+1], count + 1, result + next_num, i + 1, next_num)\n",
    "                    dfs(path + \"-\" + num[begin:i+1], count + 1, result - next_num, i + 1, -next_num)\n",
    "                    dfs(path + \"*\" + num[begin:i+1], count + 1, result - prev + next_num * prev, i + 1, next_num * prev)\n",
    "        dfs(\"\", 0, 0, 0, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "\n",
    "        ans = []\n",
    "        def backtrack(expr, i, res, last):\n",
    "            if i == n:\n",
    "                if res == target:\n",
    "                    ans.append(''.join(map(str, expr)))\n",
    "                return\n",
    "        \n",
    "            cur = len(expr)\n",
    "\n",
    "            val = 0\n",
    "            for j in range(i, n):\n",
    "                if j > i and num[i] == '0':\n",
    "                    break\n",
    "                val = val * 10 + int(num[j])\n",
    "                if i == 0:\n",
    "                    backtrack(expr + [val], j + 1, val, val)\n",
    "                else:\n",
    "                    backtrack(expr + ['+', val], j + 1, res + val, val)\n",
    "                    backtrack(expr + ['-', val], j + 1, res - val, -val)\n",
    "                    backtrack(expr + ['*', val], j + 1, res - last + last * val, last * val)\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "\n",
    "        def backtrack(expr, i, res, mul):\n",
    "            if i == n:\n",
    "                if res == target:\n",
    "                    ans.append(''.join(expr))\n",
    "                return\n",
    "            signIndex = len(expr)\n",
    "            if i > 0:\n",
    "                expr.append('')\n",
    "            val = 0\n",
    "            for j in range(i, n):\n",
    "                if j > i and num[i] == '0':\n",
    "                    break\n",
    "                val = val * 10 + int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i == 0:\n",
    "                    backtrack(expr, j + 1, val, val)\n",
    "                else:\n",
    "                    expr[signIndex] = '+'\n",
    "                    backtrack(expr, j + 1, res + val, val)\n",
    "                    expr[signIndex] = '-'\n",
    "                    backtrack(expr, j + 1, res - val, -val)\n",
    "                    expr[signIndex] = '*'\n",
    "                    backtrack(expr, j + 1, res - mul + mul * val, mul * val)\n",
    "            del expr[signIndex:]\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        self.ans = []\n",
    "        n = len(num)\n",
    "        def dfs(pre, ind):\n",
    "            if len(pre[-1]) >= 2 and pre[-1][0] == '0':\n",
    "                return \n",
    "            if ind == n:\n",
    "                if eval(''.join(pre)) == target:\n",
    "                    self.ans.append(''.join(pre))\n",
    "                return\n",
    "            \n",
    "            if pre[-1] not in ['+', '-', '*']:\n",
    "                cur = pre.copy()\n",
    "                cur[-1] += num[ind]\n",
    "                dfs(cur, ind+1)\n",
    "    \n",
    "                for add in ['+', '-', '*']:\n",
    "                    dfs(pre+[add]+[num[ind]], ind+1)\n",
    "            else:\n",
    "                dfs(pre+[num[ind]], ind+1)\n",
    "            return\n",
    "\n",
    "        dfs([num[0]], 1)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        \"\"\"\n",
    "        n=len(num)\n",
    "        ans=[]\n",
    "        \n",
    "        def backtrack(expr,i,res,mul):\n",
    "            if i==n:\n",
    "                if res==target:\n",
    "                    ans.append(\"\".join(expr))\n",
    "                return\n",
    "            \n",
    "            signIndex=len(expr)\n",
    "            if i>0:\n",
    "                expr.append(\"\")\n",
    "            val=0\n",
    "            for j in range(i,n):\n",
    "                if j>i and num[i]==\"0\":\n",
    "                    break\n",
    "                val=val*10+int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i==0:\n",
    "                    backtrack(expr,j+1,val,val)\n",
    "                else:\n",
    "                    expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val)\n",
    "                    expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val)\n",
    "                    expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val)\n",
    "            del expr[signIndex:]\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return ans\n",
    "        \"\"\"\n",
    "        n = len(num)\n",
    "        def dfs(start, prefix, value, prev):\n",
    "            if start == n:\n",
    "                if value == target:\n",
    "                    ans.append(prefix)\n",
    "                return\n",
    "            for end in range(start, n): # [start, end] 是当前考虑的数字字符串\n",
    "                string = num[start:end + 1]\n",
    "                number = int(string)\n",
    "                if end > start and num[start] == '0': break # 不能以 0 开头 , 后面不用再试了\n",
    "                if start == 0:\n",
    "                    dfs(end + 1, string, number, number)\n",
    "                else: # 剪枝，后面的数字绝对值最大的是全部连着也就是num[start:]，若它的值都小于与目标的差值，\n",
    "\t\t\t\t\t# 则只能进行乘法计算，希望前面的数字和后面相乘后的值会大于两者差值\n",
    "                    if int(num[start:]) >= abs(target - value):\n",
    "                        dfs(end + 1, prefix + '+' + string, value + number, number)\n",
    "                        dfs(end + 1, prefix + '-' + string, value - number, -number)\n",
    "                    dfs(end + 1, prefix + '*' + string, value - prev + prev * number, prev * number)\n",
    "\n",
    "        ans = []\n",
    "        dfs(0, '', 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        ans = []\n",
    "        \n",
    "        def dfs(expr, pos, res, mul):\n",
    "            if pos == len(num):\n",
    "                if res == target:\n",
    "                    ans.append(\"\".join(expr))\n",
    "                return\n",
    "            signIdx = len(expr)\n",
    "            expr.append(\"\")\n",
    "            \n",
    "            val = 0\n",
    "            for i in range(pos, len(num)):\n",
    "                if i > pos and num[pos] == \"0\":\n",
    "                    break\n",
    "                expr.append(num[i])\n",
    "                val = val * 10 + int(num[i])\n",
    "                if pos == 0:\n",
    "                    dfs(expr, i + 1, val, val)\n",
    "                else:\n",
    "                    expr[signIdx] = \"+\"\n",
    "                    dfs(expr, i + 1, res + val, val)\n",
    "                    expr[signIdx] = \"-\"\n",
    "                    dfs(expr, i + 1, res - val, -val)\n",
    "                    expr[signIdx] = \"*\"\n",
    "                    dfs(expr, i + 1, res + mul * val - mul, mul * val)\n",
    "\n",
    "            del expr[signIdx: ]\n",
    "        \n",
    "        dfs([], 0, 0, 0)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "\n",
    "        ans = []\n",
    "        def dfs(expr, curSum, prev, pos):\n",
    "            # print(expr, curSum, prev, pos)\n",
    "            if pos == len(num) and curSum == target:\n",
    "                # print(expr, curSum, prev)\n",
    "                ans.append(\"\".join(expr))\n",
    "                return\n",
    "            signIdx = len(expr)\n",
    "            expr.append(\"\")\n",
    "            val = 0\n",
    "            for i in range(pos, len(num)):\n",
    "                # print(expr, i, curSum, prev)\n",
    "                if i > pos and num[pos] == \"0\":\n",
    "                    break\n",
    "                val = val * 10 + int(num[i])\n",
    "                expr.append(str(num[i]))\n",
    "                if pos == 0:\n",
    "                    dfs(expr, curSum + val, val, i + 1)\n",
    "                else:\n",
    "                    expr[signIdx] = \"+\"\n",
    "                    dfs(expr, curSum + val, val, i + 1)\n",
    "                    expr[signIdx] = \"-\"\n",
    "                    dfs(expr, curSum - val, -val, i + 1)\n",
    "                    expr[signIdx] = \"*\"\n",
    "                    dfs(expr, curSum + prev * val - prev, prev * val, i + 1)\n",
    "            del expr[signIdx:]\n",
    "            \n",
    "        \n",
    "        dfs([], 0, 0, 0)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        def cal(nums, express, pre_num, cur_ans):\n",
    "            n = len(nums)\n",
    "            if n == 0:\n",
    "                if cur_ans == target:\n",
    "                    res.append(express)\n",
    "                return\n",
    "            for i in range(1, n+1):\n",
    "                if i > 1 and nums[0] == '0':\n",
    "                    break\n",
    "                cur_num = int(nums[:i])\n",
    "                if express == '':\n",
    "                    cal(nums[i:], nums[:i], cur_num, cur_num)\n",
    "                else:\n",
    "                    if int(nums) >= abs(cur_ans - target):  # 剪枝\n",
    "                        cal(nums[i:], express+'+'+nums[:i], cur_num, cur_ans+cur_num)\n",
    "                        cal(nums[i:], express+'-'+nums[:i], -cur_num, cur_ans-cur_num)\n",
    "                    cal(nums[i:], express+'*'+nums[:i], pre_num*cur_num, cur_ans-pre_num+pre_num*cur_num)\n",
    "            \n",
    "        res = []\n",
    "        cal(num, '', 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        # 给定数字字符串，在数字减添加运算符，使得结果等于target，返回所有可行表达式\n",
    "\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "\n",
    "        def dfs(expr: List[str], i:int, res:int, mul:int):\n",
    "            if i == n:\n",
    "                if res == target:\n",
    "                    ans.append(''.join(expr))\n",
    "                return \n",
    "            signIndex = len(expr)\n",
    "            if i > 0:\n",
    "                expr.append('') # 占位\n",
    "            val = 0\n",
    "            for j in range(i, n):\n",
    "                if j > i and num[i] == '0':\n",
    "                    break\n",
    "                val = val * 10 + int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i == 0:\n",
    "                    dfs(expr, j + 1, val, val)\n",
    "                else:\n",
    "                    expr[signIndex] = '+'; dfs(expr, j + 1, res + val, val)\n",
    "                    expr[signIndex] = '-'; dfs(expr, j + 1, res - val, -val)\n",
    "                    expr[signIndex] = '*'; dfs(expr, j + 1, res - mul + mul * val, mul * val)\n",
    "            del expr[signIndex:]\n",
    "        dfs([], 0, 0, 0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        res = []\n",
    "\n",
    "        def backtrack(i, path, cur, pre):\n",
    "            if i>=len(num):\n",
    "                if cur == target:\n",
    "                    res.append(path)\n",
    "            else:\n",
    "                for j in range(i, len(num)):\n",
    "                    if j>i and num[i] == '0':\n",
    "                        break\n",
    "\n",
    "                    v = int(num[i:j+1])\n",
    "                    if i == 0:\n",
    "                        backtrack(j+1, str(v), v, v)\n",
    "                    else:\n",
    "                        backtrack(j+1, path+'+'+str(v), cur+v, v)\n",
    "                        backtrack(j+1, path+'-'+str(v), cur-v, -v)\n",
    "                        backtrack(j+1, path+'*'+str(v), cur-pre+pre*v, pre*v)\n",
    "\n",
    "        backtrack(0, '', 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        ln = len(num)\n",
    "        ans =[]\n",
    "        def backtrack(expr:List[str],index:int,res:int,mul:int):\n",
    "            if index == ln:\n",
    "                if res == target:\n",
    "                    ans.append(\"\".join(expr))\n",
    "                return\n",
    "            l_str = len(expr)\n",
    "            expr.append(\"\")\n",
    "            cur_value = 0\n",
    "            for next_index in range(index,ln):\n",
    "                if num[index]==\"0\" and next_index>index:\n",
    "                    break\n",
    "                cur_value = cur_value*10 + int(num[next_index])\n",
    "                expr.append(num[next_index])\n",
    "                if index==0:\n",
    "                    backtrack(expr,next_index+1,res+cur_value,cur_value)\n",
    "                    continue\n",
    "                # 三种情况分类讨论\n",
    "                expr[l_str]=\"+\"\n",
    "                backtrack(expr,next_index+1,res+cur_value,cur_value)\n",
    "                expr[l_str]=\"-\"\n",
    "                backtrack(expr,next_index+1,res-cur_value,-cur_value)\n",
    "                expr[l_str]=\"*\"\n",
    "                backtrack(expr,next_index+1,res-mul+mul*cur_value,mul*cur_value)\n",
    "            del expr[l_str:]\n",
    "        backtrack([],0,0,0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        \"\"\"\n",
    "        n=len(num)\n",
    "        ans=[]\n",
    "        \n",
    "        def backtrack(expr,i,res,mul):\n",
    "            if i==n:\n",
    "                if res==target:\n",
    "                    ans.append(\"\".join(expr))\n",
    "                return\n",
    "            \n",
    "            signIndex=len(expr)\n",
    "            if i>0:\n",
    "                expr.append(\"\")\n",
    "            val=0\n",
    "            for j in range(i,n):\n",
    "                if j>i and num[i]==\"0\":\n",
    "                    break\n",
    "                val=val*10+int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i==0:\n",
    "                    backtrack(expr,j+1,val,val)\n",
    "                else:\n",
    "                    expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val)\n",
    "                    expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val)\n",
    "                    expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val)\n",
    "            del expr[signIndex:]\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return ans\n",
    "        \"\"\"\n",
    "        n = len(num)\n",
    "        def dfs(start, prefix, value, prev):\n",
    "            if start == n:\n",
    "                if value == target:\n",
    "                    ans.append(prefix)\n",
    "                return\n",
    "            for end in range(start, n): # [start, end] 是当前考虑的数字字符串\n",
    "                string = num[start:end + 1]\n",
    "                number = int(string)\n",
    "                if end > start and num[start] == '0': break # 不能以 0 开头 , 后面不用再试了\n",
    "                if start == 0:\n",
    "                    dfs(end + 1, string, number, number)\n",
    "                else: # 剪枝，后面的数字绝对值最大的是全部连着也就是num[start:]，若它的值都小于与目标的差值，\n",
    "\t\t\t\t\t# 则只能进行乘法计算，希望前面的数字和后面相乘后的值会大于两者差值\n",
    "                    if int(num[start:]) >= abs(target - value):\n",
    "                        dfs(end + 1, prefix + '+' + string, value + number, number)\n",
    "                        dfs(end + 1, prefix + '-' + string, value - number, -number)\n",
    "                    dfs(end + 1, prefix + '*' + string, value - prev + prev * number, prev * number)\n",
    "\n",
    "        ans = []\n",
    "        dfs(0, '', 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        nums = list(num)\n",
    "        ans = []\n",
    "        t = 0\n",
    "        for i in range(len(nums)):  # 尝试0~i前缀作为第一部分\n",
    "            # print(i)\n",
    "            t = t * 10 + ord(nums[i]) - ord('0')\n",
    "            self.process(nums, target, i+1, [str(t)], 0, t, ans)\n",
    "            if t == 0:  # 0不能作为开头和后面的数形成新数\n",
    "                break\n",
    "        return ans\n",
    "\n",
    "    # nums 存放原始的数据\n",
    "    # target 最终要达成的数据目标\n",
    "    # index 对nums的索引\n",
    "    # path 之前做的决定，已经从左往右依次填写的字符在其中，可能含有'0'~'9' 与 * - +\n",
    "    # left 已经确认不会变的部分\n",
    "    # cur 当前可能会被的部分\n",
    "    def process(self, nums, target, index, path, left, cur, ans):\n",
    "        if index == len(nums):\n",
    "            if left + cur == target:\n",
    "                ans.append(''.join(path))\n",
    "            return\n",
    "        t = 0\n",
    "        for i in range(index, len(nums)):\n",
    "            # print(i)\n",
    "            t = t * 10 + ord(nums[i]) - ord('0')\n",
    "            path.append('+')\n",
    "            path.append(str(t))\n",
    "            self.process(nums, target, i+1, path, left+cur, t, ans)\n",
    "            path[-2] = '-'\n",
    "            # path[-1] = t\n",
    "            self.process(nums, target, i+1, path, left+cur, -t, ans)\n",
    "            path[-2] = '*'\n",
    "            # path.append(t)\n",
    "            self.process(nums, target, i+1, path, left, cur * t, ans)\n",
    "            path.pop()\n",
    "            path.pop()\n",
    "            if nums[index] == '0':  # 0开头的话，不能和后面拼接在一起，形成新的数\n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        def cal(nums, express, pre_num, cur_ans):\n",
    "            n = len(nums)\n",
    "            if n == 0:\n",
    "                if cur_ans == target:\n",
    "                    res.append(express)\n",
    "                return\n",
    "            for i in range(1, n+1):\n",
    "                if i > 1 and nums[0] == '0':\n",
    "                    break\n",
    "                cur_num = int(nums[:i])\n",
    "                if express == '':\n",
    "                    cal(nums[i:], nums[:i], cur_num, cur_num)\n",
    "                else:\n",
    "                    # if int(nums) >= abs(cur_ans - target):  # 剪枝\n",
    "                    cal(nums[i:], express+'+'+nums[:i], cur_num, cur_ans+cur_num)\n",
    "                    cal(nums[i:], express+'-'+nums[:i], -cur_num, cur_ans-cur_num)\n",
    "                    cal(nums[i:], express+'*'+nums[:i], pre_num*cur_num, cur_ans-pre_num+pre_num*cur_num)\n",
    "            \n",
    "        res = []\n",
    "        cal(num, '', 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        res = []\n",
    "\n",
    "        def backtrack(i, path, cur, prev):\n",
    "            if i>=len(num):\n",
    "                if cur == target:\n",
    "                    res.append(path)\n",
    "            else:\n",
    "                for j in range(i, len(num)):\n",
    "                    if j>i and num[i] == '0':\n",
    "                        break\n",
    "\n",
    "                    v = int(num[i:j+1])\n",
    "                    if i == 0:\n",
    "                        backtrack(j+1, str(v), v, v)\n",
    "                    else:\n",
    "                        backtrack(j+1, path+'+'+str(v), cur+v, v)\n",
    "                        backtrack(j+1, path+'-'+str(v), cur-v, -v)\n",
    "                        backtrack(j+1, path+'*'+str(v), cur-prev+prev*v, prev*v)\n",
    "\n",
    "        backtrack(0, '', 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n=len(num)\n",
    "        ans=[]\n",
    "        def backTrace(expr:List[str],i:int,res:int,mul:int):\n",
    "            if i==n:\n",
    "                if res==target:ans.append(''.join(expr))\n",
    "                return \n",
    "            signIndex=len(expr)\n",
    "            if i>0:expr.append('')\n",
    "            val=0\n",
    "            for j in range(i,n):\n",
    "                if j>i and num[i]=='0':break\n",
    "                val=val*10+int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i==0:backTrace(expr,j+1,val,val)\n",
    "                else:\n",
    "                    expr[signIndex]='+';backTrace(expr,j+1,res+val,val)\n",
    "                    expr[signIndex]='-';backTrace(expr,j+1,res-val,-val)\n",
    "                    expr[signIndex]='*';backTrace(expr,j+1,res-mul+mul*val,mul*val)\n",
    "            del expr[signIndex:]\n",
    "        backTrace([],0,0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "        def dfs(expr,i,res,mul):\n",
    "            if i == n:\n",
    "                if res == target:\n",
    "                    ans.append(''.join(expr))\n",
    "                return \n",
    "            idx = len(expr)\n",
    "            if i >0:\n",
    "                expr.append('')\n",
    "            val = 0\n",
    "            for j in range(i,n):\n",
    "                if j > i and num[i] == '0':\n",
    "                    break \n",
    "                val = val*10 + int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i == 0:\n",
    "                    dfs(expr,j+1,val,val)\n",
    "                else:\n",
    "                    expr[idx] = '+'\n",
    "                    dfs(expr,j+1,res+val,val)\n",
    "                    expr[idx] = '-'\n",
    "                    dfs(expr,j+1,res-val,-val)\n",
    "                    expr[idx] = '*'\n",
    "                    dfs(expr,j+1,res-mul+mul*val,mul*val)\n",
    "            del expr[idx:]\n",
    "        dfs([],0,0,0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n =len(num)\n",
    "        res = []\n",
    "        def dfs(start, path, total, last):\n",
    "            if start >= n:\n",
    "                if start == n and total == target:\n",
    "                    res.append(path)\n",
    "                return\n",
    "            for i in range(start, n):\n",
    "                tmp = num[start: i + 1] # put those 3 lines here\n",
    "                if len(tmp) > 1 and tmp[0] == \"0\": # single 0 is ok\n",
    "                    continue\n",
    "                if start == 0:\n",
    "                    dfs(i+1, path + tmp, total + int(tmp), int(tmp))\n",
    "                else:\n",
    "                    # if tmp[0] == \"0\": wrong\n",
    "                    #     continue\n",
    "                    dfs(i +1, path + \"+\" +tmp,  total + int(tmp), int(tmp))\n",
    "                    dfs(i+1, path + \"-\" +tmp,  total - int(tmp), -int(tmp))\n",
    "                    dfs(i+1, path + \"*\" + tmp, total -last + last*int(tmp), last*int(tmp))\n",
    "                  \n",
    "        dfs(0, \"\", 0, 0)\n",
    "        return res\n",
    "# num = \"0\", target=0, [\"0+0\",\"0-0\",\"0*0\",\"00\"] is wrong should be [\"0*0\",\"0+0\",\"0-0\"]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        \n",
    "        n = len(num)\n",
    "        ans = []\n",
    "        \n",
    "        def dfs(expr, idx, sums, pre):\n",
    "            nonlocal n\n",
    "            if idx == n:\n",
    "                if sums == target:\n",
    "                    ans.append(\"\".join(expr))\n",
    "                return\n",
    "            signIdx = len(expr)\n",
    "            expr.append(\"\")\n",
    "            x = 0\n",
    "            for i in range(idx, n):\n",
    "                if i > idx and num[idx] == \"0\":\n",
    "                    break\n",
    "                expr.append(num[i])\n",
    "                x = x * 10 + int(num[i])\n",
    "                if idx == 0:\n",
    "                    dfs(expr, i + 1, x, x)\n",
    "                else:\n",
    "                    expr[signIdx] = \"+\"\n",
    "                    dfs(expr, i + 1, sums + x, x)\n",
    "                    expr[signIdx] = \"-\"\n",
    "                    dfs(expr, i + 1, sums - x, -x)\n",
    "                    expr[signIdx] = \"*\"\n",
    "                    dfs(expr, i + 1, sums - pre + pre * x, pre * x)\n",
    "            del expr[signIdx:]\n",
    "            return\n",
    "        \n",
    "        dfs([], 0, 0, 0)\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n, ans = len(num), set()\n",
    "        def dfs(expression, curIdx):\n",
    "            if curIdx == n:\n",
    "                try:\n",
    "                    if eval(expression) == target:\n",
    "                        ans.add(expression)\n",
    "                except:\n",
    "                    pass\n",
    "            else:\n",
    "                for j in range(curIdx, n):\n",
    "                    if j - curIdx >= 1 and num[curIdx:j+1][0] == '0': # 不能存在0开头的超过1位的数字 -- 不应该包含前导零\n",
    "                        continue\n",
    "                    nextExp = expression + num[curIdx:j+1]\n",
    "                    if j == n - 1: # 最后一个数字后面不加运算符\n",
    "                        dfs(nextExp, j + 1)\n",
    "                    else:\n",
    "                        for op in ['+', '-', '*']:\n",
    "                            dfs(nextExp + op, j + 1)\n",
    "        dfs('', 0)\n",
    "        return list(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "\n",
    "        def backtrack(expr: List[str], i: int, res: int, mul: int):\n",
    "            if i == n:\n",
    "                if res == target:\n",
    "                    ans.append(''.join(expr))\n",
    "                return\n",
    "            signIndex = len(expr)\n",
    "            if i > 0:\n",
    "                expr.append('')  # 占位，下面填充符号\n",
    "            val = 0\n",
    "            for j in range(i, n):  # 枚举截取的数字长度（取多少位）\n",
    "                if j > i and num[i] == '0':  # 数字可以是单个 0 但不能有前导零\n",
    "                    break\n",
    "                val = val * 10 + int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i == 0:  # 表达式开头不能添加符号\n",
    "                    backtrack(expr, j + 1, val, val)\n",
    "                else:  # 枚举符号\n",
    "                    expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val)\n",
    "                    expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val)\n",
    "                    expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val)\n",
    "            del expr[signIndex:]\n",
    "\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        def dfs(index, s, res, pre):\n",
    "            if index == n:\n",
    "                if res == target:\n",
    "                    ans.append(s)\n",
    "                return\n",
    "            for i in range(index, n):\n",
    "                if i > index and num[index] == '0':\n",
    "                    break\n",
    "                t = num[index:i + 1]\n",
    "                cur = int(t)\n",
    "                dfs(i + 1, s + '+' + t, res + cur, cur)\n",
    "                dfs(i + 1, s + '-' + t, res - cur, -cur)\n",
    "                dfs(i + 1, s + '*' + t, res + pre * (cur - 1), pre * cur)\n",
    "        \n",
    "        n = len(num)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if i > 0 and num[0] == '0':\n",
    "                break\n",
    "            t = num[:i + 1]\n",
    "            cur = int(t)\n",
    "            dfs(i + 1, t, cur, cur)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        res = [] \n",
    "        n = len(num)\n",
    "        # start: 处理到了数组中那个数字. path: local结果集\n",
    "        # last: 一个表达式. 1+2*3, last=6; 1+2-3,last=-3\n",
    "        # total：目前的结果\n",
    "        def dfs(start, path, last, total):\n",
    "            # 递归结束，收集local结果\n",
    "            if start >= n:\n",
    "                if total == target:\n",
    "                    res.append(path) \n",
    "                return\n",
    "\n",
    "            for i in range(start, n): # for 有尽头，不会死循环\n",
    "                x = num[start: i + 1]\n",
    "\n",
    "                if len(x) > 1 and x[0] == '0': # 避免前缀0的情况\n",
    "                    return\n",
    "\n",
    "                x = int(x)\n",
    "                # 不用考虑第0个数字前添加符号\n",
    "                if start == 0: \n",
    "                     dfs(i + 1, str(x), x, x)\n",
    "\n",
    "                else: # 添加3种不同符号在idx前 \n",
    "                    dfs(i + 1, path + '+' + str(x), x, total + x)\n",
    "                    dfs(i + 1, path + '-' + str(x), -x, total - x)\n",
    "                    # 2-3 *5 =》 -1(total since 2- 3 =1) -(-3)(last) + (-3 *5) (last*x).\n",
    "                    # 然后把-3*5当作last传个下个dfs\n",
    "                    dfs(i + 1, path + '*' + str(x), last * x, total - last + last * x)\n",
    "        dfs(0, \"\", 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "        for i in range(1 << (n - 1), 1 << n):\n",
    "            cur = []\n",
    "            start = 0\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    if num[start] == '0' and j > start:\n",
    "                        break\n",
    "                    cur.append(num[start:j + 1])\n",
    "                    start = j + 1\n",
    "            else:\n",
    "                for comb in product([\"+\", \"-\", \"*\"], repeat=len(cur) - 1):\n",
    "                    s = cur[0] + ''.join(op + digit for op, digit in zip(comb, cur[1:]))\n",
    "                    if eval(s) == target:\n",
    "                        ans.append(s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "\n",
    "        def backtrack(expr: List[str], i: int, res: int, mul: int):\n",
    "            if i == n:\n",
    "                if res == target:\n",
    "                    ans.append(''.join(expr))\n",
    "                return\n",
    "            signIndex = len(expr)\n",
    "            if i > 0:\n",
    "                expr.append('')  # 占位，下面填充符号\n",
    "            val = 0\n",
    "            for j in range(i, n):  # 枚举截取的数字长度（取多少位）\n",
    "                if j > i and num[i] == '0':  # 数字可以是单个 0 但不能有前导零\n",
    "                    break\n",
    "                val = val * 10 + int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i == 0:  # 表达式开头不能添加符号\n",
    "                    backtrack(expr, j + 1, val, val)\n",
    "                else:  # 枚举符号\n",
    "                    expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val)\n",
    "                    expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val)\n",
    "                    expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val)\n",
    "            del expr[signIndex:]\n",
    "\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        ans = [[]]\n",
    "        lens = len(num)\n",
    "        def cal(calstr):\n",
    "            l = r = 0\n",
    "            lenc = len(calstr)\n",
    "            callist = []\n",
    "            while l < lenc:\n",
    "                if calstr[l].isdigit():\n",
    "                    r = l\n",
    "                    while r < lenc and calstr[r].isdigit():\n",
    "                        r += 1\n",
    "                    callist.append(calstr[l:r])\n",
    "                    l = r\n",
    "                else:\n",
    "                    callist.append(calstr[l])\n",
    "                    l += 1\n",
    "            numstack = deque([])\n",
    "            opestack = deque([])\n",
    "            for item in callist:\n",
    "                if item.isdigit():\n",
    "                    numstack.append(int(item))\n",
    "                else:\n",
    "                    opestack.append(item)\n",
    "            # print(callist, numstack, opestack)\n",
    "            while opestack:\n",
    "                if opestack[0] == '*':\n",
    "                    opestack.popleft()\n",
    "                    num1 = numstack[0]\n",
    "                    numstack.popleft()\n",
    "                    num2 = numstack[0]\n",
    "                    numstack.popleft()\n",
    "                    numstack.appendleft(num1*num2)\n",
    "                else:\n",
    "                    ope1 = opestack[0]\n",
    "                    opestack.popleft()\n",
    "                    num1 = numstack[0]\n",
    "                    numstack.popleft()\n",
    "                    num2 = numstack[0]\n",
    "                    numstack.popleft()\n",
    "                    if opestack and opestack[0] == '*':\n",
    "                        opestack.popleft()\n",
    "                        num3 = numstack[0]\n",
    "                        numstack.popleft()\n",
    "                        numstack.appendleft(num2*num3)\n",
    "                        numstack.appendleft(num1)\n",
    "                        opestack.appendleft(ope1)\n",
    "                    elif ope1 == '+':\n",
    "                        numstack.appendleft(num1+num2)\n",
    "                    else:\n",
    "                        numstack.appendleft(num1-num2)\n",
    "                # print(numstack, opestack)\n",
    "            return numstack[0]\n",
    "        def dfs(res, idx):\n",
    "            if idx >= lens:\n",
    "                if cal(res) == target:\n",
    "                    ans[0].append(res)\n",
    "                return\n",
    "            for r in range(idx, lens):\n",
    "                if num[idx] == '0' and r - idx > 0:\n",
    "                    break\n",
    "                key = int(num[idx: r+1])\n",
    "                if idx == 0:\n",
    "                    dfs(res+num[idx: r+1], r+1)\n",
    "                else:\n",
    "                    dfs(res+'+'+num[idx: r+1], r+1)\n",
    "                    dfs(res+'-'+num[idx: r+1], r+1)\n",
    "                    dfs(res+'*'+num[idx: r+1], r+1)       \n",
    "        dfs('', 0)\n",
    "        # print(cal('1-2*3-4*5-6*7-8*9'))\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\r\n",
    "        n, ans = len(num), []\r\n",
    "        def f(exp, res, idx, mul):\r\n",
    "            if idx == n:\r\n",
    "                if res == target:\r\n",
    "                    ans.append(''.join(exp))\r\n",
    "                return\r\n",
    "            si, val = len(exp), 0\r\n",
    "            if idx > 0:\r\n",
    "                exp.append('')\r\n",
    "            for i in range(idx, n):\r\n",
    "                if num[idx] == '0' and i > idx:\r\n",
    "                    break\r\n",
    "                val = val * 10 + int(num[i])\r\n",
    "                exp.append(num[i])\r\n",
    "                if idx == 0:\r\n",
    "                    f(exp, val, i + 1, val)\r\n",
    "                else:\r\n",
    "                    exp[si] = '+'\r\n",
    "                    f(exp, res + val, i + 1, val)\r\n",
    "                    exp[si] = '-'\r\n",
    "                    f(exp, res - val, i + 1, -val)\r\n",
    "                    exp[si] = '*'\r\n",
    "                    f(exp, res - mul + mul * val, i + 1, mul * val)\r\n",
    "            del exp[si:]\r\n",
    "        f([], 0, 0, 0)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        def dfs(nums, i, res, mul):\n",
    "            if i == n:\n",
    "                if res == target:\n",
    "                    ans.append(''.join(nums))\n",
    "                return\n",
    "            ll = len(nums)\n",
    "            for j in range(i + 1, n+1):\n",
    "                tmp = num[i:j]\n",
    "                if len(tmp)>1 and tmp.startswith('0'): return\n",
    "                if i == 0:\n",
    "                    nums.append(tmp)\n",
    "                    dfs(nums, j, int(tmp), int(tmp))\n",
    "                    nums.pop(-1)\n",
    "                else:\n",
    "                    # +号\n",
    "                    nums.append('+')\n",
    "                    nums.append(tmp)\n",
    "                    dfs(nums, j, res + int(tmp), int(tmp))\n",
    "                    nums.pop(-1)\n",
    "                    nums.pop(-1)\n",
    "                    # -号\n",
    "                    nums.append('-')\n",
    "                    nums.append(tmp)\n",
    "                    dfs(nums, j, res - int(tmp), -int(tmp))\n",
    "                    nums.pop(-1)\n",
    "                    nums.pop(-1)\n",
    "                    # *号\n",
    "                    nums.append('*')\n",
    "                    nums.append(tmp)\n",
    "                    dfs(nums, j, res - mul + mul * int(tmp), mul * int(tmp))\n",
    "                    nums.pop(-1)\n",
    "                    nums.pop(-1)\n",
    "            while len(nums) > ll:\n",
    "                nums.pop(-1)\n",
    "\n",
    "        ans = []\n",
    "        n = len(num)\n",
    "        dfs([], 0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ops = [\"*\", \"+\", \"\", \"-\"]\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        def dfs(idx, sign, curv, val, path):\n",
    "            c = num[idx]\n",
    "            curv = 10 * curv + int(c)\n",
    "            if idx == n - 1:\n",
    "                if sign * curv + val == target:\n",
    "                    path.append(num[idx])\n",
    "                    ans.append(\"\".join(path))\n",
    "                    path.pop()\n",
    "                return\n",
    "            for i in (-1, 0, 1, 2):\n",
    "                path.append(num[idx] + ops[i])\n",
    "                if not i:\n",
    "                    dfs(idx+1, sign * curv, 0, val, path)\n",
    "                elif i < 2:\n",
    "                    dfs(idx+1, i, 0, val + sign * curv, path)\n",
    "                elif curv or c != '0':\n",
    "                    dfs(idx+1, sign, curv, val, path)\n",
    "                path.pop()\n",
    "\n",
    "        ans = []\n",
    "        n = len(num)\n",
    "        dfs(0, 1, 0, 0, [])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        \"\"\"\n",
    "        n=len(num)\n",
    "        ans=[]\n",
    "        \n",
    "        def backtrack(expr,i,res,mul):\n",
    "            if i==n:\n",
    "                if res==target:\n",
    "                    ans.append(\"\".join(expr))\n",
    "                return\n",
    "            \n",
    "            signIndex=len(expr)\n",
    "            if i>0:\n",
    "                expr.append(\"\")\n",
    "            val=0\n",
    "            for j in range(i,n):\n",
    "                if j>i and num[i]==\"0\":\n",
    "                    break\n",
    "                val=val*10+int(num[j])\n",
    "                expr.append(num[j])\n",
    "                if i==0:\n",
    "                    backtrack(expr,j+1,val,val)\n",
    "                else:\n",
    "                    expr[signIndex] = '+'; backtrack(expr, j + 1, res + val, val)\n",
    "                    expr[signIndex] = '-'; backtrack(expr, j + 1, res - val, -val)\n",
    "                    expr[signIndex] = '*'; backtrack(expr, j + 1, res - mul + mul * val, mul * val)\n",
    "            del expr[signIndex:]\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return ans\n",
    "        \"\"\"\n",
    "        n = len(num)\n",
    "        def dfs(start, prefix, value, prev):\n",
    "            if start == n:\n",
    "                if value == target:\n",
    "                    ans.append(prefix)\n",
    "                return\n",
    "            for end in range(start, n): # [start, end] 是当前考虑的数字字符串\n",
    "                string = num[start:end + 1]\n",
    "                number = int(string)\n",
    "                if end > start and num[start] == '0': break # 不能以 0 开头 , 后面不用再试了\n",
    "                if start == 0:\n",
    "                    dfs(end + 1, string, number, number)\n",
    "                else: # 剪枝，后面的数字绝对值最大的是全部连着也就是num[start:]，若它的值都小于与目标的差值，\n",
    "\t\t\t\t\t# 则只能进行乘法计算，希望前面的数字和后面相乘后的值会大于两者差值\n",
    "                    if int(num[start:]) >= abs(target - value):\n",
    "                        dfs(end + 1, prefix + '+' + string, value + number, number)\n",
    "                        dfs(end + 1, prefix + '-' + string, value - number, -number)\n",
    "                    dfs(end + 1, prefix + '*' + string, value - prev + prev * number, prev * number)\n",
    "\n",
    "        ans = []\n",
    "        dfs(0, '', 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ops = [\"*\", \"+\", \"\", \"-\"]\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        def dfs(idx, sign, curv, val, path):\n",
    "            c = num[idx]\n",
    "            curv = 10 * curv + int(c)\n",
    "            if idx == n - 1:\n",
    "                if sign * curv + val == target:\n",
    "                    path.append(num[idx])\n",
    "                    ans.append(\"\".join(path))\n",
    "                    path.pop()\n",
    "                return\n",
    "            for i in (-1, 0, 1, 2):\n",
    "                path.append(num[idx] + ops[i])\n",
    "                if not i:\n",
    "                    dfs(idx+1, sign * curv, 0, val, path)\n",
    "                elif i < 2:\n",
    "                    dfs(idx+1, i, 0, val + sign * curv, path)\n",
    "                elif curv or c != '0':\n",
    "                    dfs(idx+1, sign, curv, val, path)\n",
    "                path.pop()\n",
    "\n",
    "        ans = []\n",
    "        n = len(num)\n",
    "        dfs(0, 1, 0, 0, [])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n, ans = len(num), set()\n",
    "        def dfs(expression, curIdx):\n",
    "            if curIdx == n:\n",
    "                try:\n",
    "                    if eval(expression) == target:\n",
    "                        ans.add(expression)\n",
    "                except:\n",
    "                    pass\n",
    "            else:\n",
    "                for j in range(curIdx, n):\n",
    "                    if j - curIdx >= 1 and num[curIdx:j+1][0] == '0':\n",
    "                        continue\n",
    "                    nextExp = expression + num[curIdx:j+1]\n",
    "                    if j == n - 1: # 最后一个数字后面不加运算符\n",
    "                        dfs(nextExp, j + 1)\n",
    "                    else:\n",
    "                        for op in ['+', '-', '*']:\n",
    "                            dfs(nextExp + op, j + 1)\n",
    "        dfs('', 0)\n",
    "        return list(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        ops = [\"*\", \"+\", \"\", \"-\"]\n",
    "        def dfs(idx, sign, curv, val, path):\n",
    "            c = num[idx]\n",
    "            curv = 10 * curv + int(c)\n",
    "            if idx == n - 1:\n",
    "                if sign * curv + val == target:\n",
    "                    path.append(num[idx])\n",
    "                    ans.append(\"\".join(path[:]))\n",
    "                    path.pop()\n",
    "                return\n",
    "            for i in (-1, 0, 1, 2):\n",
    "                path.append(num[idx] + ops[i])\n",
    "                if not i:\n",
    "                    dfs(idx + 1, sign * curv, 0, val, path)\n",
    "                elif i < 2:\n",
    "                    dfs(idx + 1, i, 0, val + sign * curv, path)\n",
    "                elif curv or c != '0':\n",
    "                    dfs(idx + 1, sign, curv, val, path)\n",
    "                path.pop()\n",
    "\n",
    "        ans = []\n",
    "        n = len(num)\n",
    "        dfs(0, 1, 0, 0, [])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        \"\"\"\n",
    "        time complexity: \n",
    "        递归深度：最多n层，其中n为输入字符串num的长度。\n",
    "        每层递归：最多会有3*(n-p)种递归情况，其中p是当前字符的位置。因为每个字符都可以与下一个字符进行加、减、乘运算，或者与下一个字符组成一个更大的数字，所以每个字符会产生三个递归分支。\n",
    "        合并上述两点，最坏的情况下（没有任何剪枝的情况下）时间复杂度约为O(3^n)。然而由于我们的实现中包含了一些剪枝策略（比如避免使用前导零的数字），在实际运行中的时间复杂度将要低于这个界限。\n",
    "\n",
    "        space complexity:\n",
    "        递归调用栈的深度：由于递归的最大深度是n，因此递归调用栈的空间复杂度是O(n)。\n",
    "        结果存储：在最坏的情况下，存储所有可能的表达式的空间复杂度为O(3^n)，因为可能存在3^n个有效表达式。\n",
    "        空间复杂度最坏的情况下为O(3^n + n) ≈ O(3^n)\n",
    "        \"\"\"\n",
    "        \"\"\"\n",
    "        输入：42325178\n",
    "        4 + 2 * 3 - 2 * 5  1 7 8 \n",
    "                        ^\n",
    "                        |\n",
    "                       pos             \n",
    "        \n",
    "        p=4\n",
    "        i=5,6,7 ==> new_number=1, 17, 178\n",
    "        pre_sum 是之前一个数字的计算结果，在这里是 -2（包含了运算符和）\n",
    "        cur_sum 是之前位置的计算结果，在这里是 4+2*3-2=8\n",
    "\n",
    "        关于pre_sum： \n",
    "        p=0, pre_sum=4, cur_sum=4\n",
    "        p=1, pre_sum=2, cur_sum=4+2=6\n",
    "        p=2, pre_sum=2*3=6  cur_sum=6-2+2*3=10\n",
    "        p=3, pre_sum=-2, cur_sum=10-2=8\n",
    "        \n",
    "        \"\"\"\n",
    "\n",
    "        n = len(num)\n",
    "        result = []\n",
    "\n",
    "        def dfs(p, pre_sum, cur_sum, path_list):\n",
    "            if p == n:\n",
    "                if cur_sum == target:\n",
    "                    result.append(\"\".join(path_list))  # Only join when a solution is found\n",
    "                return\n",
    "            \n",
    "            for i in range(p+1, n+1):\n",
    "                # Skipping numbers with leading zeros\n",
    "                if i == p + 1 or (i > p + 1 and num[p] != \"0\"):  \n",
    "                    new_number = int(num[p:i])\n",
    "\n",
    "                    if p == 0:\n",
    "                        path_list.append(num[p:i])  # No operator needed before first number\n",
    "                        dfs(i, new_number, new_number, path_list)\n",
    "                        path_list.pop()\n",
    "                    else:\n",
    "                        path_list.append(\"+\")\n",
    "                        path_list.append(num[p:i])\n",
    "                        dfs(i, new_number, cur_sum + new_number, path_list)\n",
    "                        path_list.pop()\n",
    "                        path_list.pop()\n",
    "\n",
    "                        path_list.append(\"-\")\n",
    "                        path_list.append(num[p:i])\n",
    "                        dfs(i, -new_number, cur_sum - new_number, path_list)\n",
    "                        path_list.pop()\n",
    "                        path_list.pop()\n",
    "\n",
    "                        # 可以写成path_list.extend([\"*\", num[p:i]])\n",
    "                        path_list.append(\"*\")\n",
    "                        path_list.append(num[p:i])\n",
    "                        dfs(i, pre_sum * new_number, cur_sum - pre_sum + pre_sum * new_number, path_list)\n",
    "                        path_list.pop()\n",
    "                        path_list.pop()\n",
    "        \n",
    "        dfs(0, 0, 0, [])\n",
    "        return result      \n",
    "\n",
    "\n",
    "        # 在Python中，字符串拼接的成本实际上是相当高的，尤其是在递归函数中，每个函数调用都创建一个新的字符串实例。这意味着上述的path + \"+\" + num[p:i]、path + \"-\" + num[p:i]以及path + \"*\" + num[p:i]都会创建新的字符串，增加时间和空间的开销\n",
    "\n",
    "        # def dfs(p, pre_sum, cur_sum, path):\n",
    "        #     if p == n:\n",
    "        #         # 不能写成 p==n and cur_sum==target，因为p==n是需要返回的\n",
    "        #         if cur_sum == target:\n",
    "        #             result.append(path)\n",
    "        #         return\n",
    "            \n",
    "        #     # get the new_number from i to end\n",
    "        #     for i in range(p+1, n+1):\n",
    "        #         if i - p > 1 and num[p] == \"0\":\n",
    "        #             continue\n",
    "\n",
    "        #         new_number = int(num[p:i])\n",
    "\n",
    "        #         if p == 0:\n",
    "        #             dfs(i, new_number, cur_sum + new_number, num[p:i])\n",
    "                \n",
    "        #         else:\n",
    "        #             dfs(i, new_number, cur_sum + new_number, path + \"+\" + num[p:i])\n",
    "        #             dfs(i, 0 - new_number, cur_sum - new_number, path + \"-\" + num[p:i])\n",
    "        #             dfs(i, pre_sum * new_number, cur_sum - pre_sum + pre_sum * new_number, path + \"*\" + num[p:i])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        if len(num) == 0:\n",
    "            return []\n",
    "        if len(num) == 1:\n",
    "            return [num] if int(num) == target else []\n",
    "        res = []\n",
    "        def recursion(deep, tmp):\n",
    "            if deep == len(num) - 1:\n",
    "                s = num[0]\n",
    "                ans = [num[0]]\n",
    "                s1 = []\n",
    "                for it, op in enumerate(tmp):\n",
    "                    s += op + num[it + 1]\n",
    "                    if op == \"\":\n",
    "                        if ans[-1] == \"0\":\n",
    "                            return\n",
    "                        ans[-1] = ans[-1] + num[it + 1]\n",
    "                    else:\n",
    "                        ans.append(num[it + 1])\n",
    "                        s1.append(op)\n",
    "                ans = list(map(int, ans))\n",
    "                ans1 = [ans[0]]\n",
    "                for it, op in enumerate(s1):\n",
    "                    if op == \"+\":\n",
    "                        ans1.append(ans[it + 1])\n",
    "                    elif op == \"-\":\n",
    "                        ans1.append(-ans[it + 1])\n",
    "                    else:\n",
    "                        ans1[-1] = ans1[-1] * ans[it + 1]\n",
    "                if sum(ans1) == target:\n",
    "                    res.append(s)\n",
    "                return\n",
    "            for op in [\"+\", \"-\", \"*\", \"\"]:\n",
    "                tmp.append(op)\n",
    "                deep += 1\n",
    "                recursion(deep, tmp)\n",
    "                tmp.pop()\n",
    "                deep -= 1\n",
    "        recursion(0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n, ans = len(num), set()\n",
    "        def dfs(expression, curIdx):\n",
    "            if curIdx == n:\n",
    "                # print(f\"expression:{expression}\")\n",
    "                try:\n",
    "                    if eval(expression) == target and len(expression) >= n:\n",
    "                        ans.add(expression)\n",
    "                except:\n",
    "                    pass\n",
    "            else:\n",
    "                for j in range(curIdx, n):\n",
    "                    if j - curIdx >= 1 and num[curIdx:j+1][0] == '0':\n",
    "                        continue\n",
    "                    nextExp = expression + num[curIdx:j+1]\n",
    "                    if j == n - 1: # 最后一个数字后面不加运算符\n",
    "                        dfs(nextExp, j + 1)\n",
    "                    else:\n",
    "                        for op in ['+', '-', '*']:\n",
    "                            dfs(nextExp + op, j + 1)\n",
    "        dfs('', 0)\n",
    "        return list(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        def calc(s):\n",
    "            opt=[]\n",
    "            exp=[]\n",
    "            num=0\n",
    "            last_is_digit=False\n",
    "            for ch in s:\n",
    "                if ch.isdigit():\n",
    "                    last_is_digit=True\n",
    "                    num=num*10+int(ch)\n",
    "                else:\n",
    "                    if last_is_digit:\n",
    "                        last_is_digit=False\n",
    "                        exp.append(num)\n",
    "                        num=0\n",
    "                    if ch=='*':\n",
    "                        opt.append(ch)\n",
    "                    else:\n",
    "                        while opt and (opt[-1]=='*' or opt[-1]=='-'):\n",
    "                            exp.append(opt.pop())\n",
    "                        opt.append(ch)\n",
    "            if last_is_digit:\n",
    "                exp.append(num)\n",
    "            while opt:\n",
    "                exp.append(opt.pop())\n",
    "            ans=0\n",
    "            st=[]\n",
    "            # print(exp)\n",
    "            for e in exp:\n",
    "                if isinstance(e,int):\n",
    "                    st.append(e)\n",
    "                else:\n",
    "                    b=st.pop()\n",
    "                    a=st.pop()\n",
    "                    if e=='-':\n",
    "                        r=a-b\n",
    "                    elif e=='+':\n",
    "                        r=a+b\n",
    "                    else:\n",
    "                        r=a*b\n",
    "                    st.append(r)\n",
    "            assert len(st)==1\n",
    "            return st[0]\n",
    "        # print(calc('1+2*3'))\n",
    "        # print(calc('3*4*5-6-2*3'))\n",
    "        # print(calc('3-4-56+2+3'))\n",
    "        def dfs(buf):\n",
    "            if '.' not in buf:\n",
    "                e=''.join(buf)\n",
    "                if calc(e)==target:\n",
    "                    ans.append(e)\n",
    "                return\n",
    "            idx=buf.index('.')\n",
    "            # print(buf,idx)\n",
    "            pre_is_zero= buf[idx-1]=='0' and (idx==1 or buf[idx-2]!='')\n",
    "            for c in ['*','','+','-',]:\n",
    "                if c=='' and pre_is_zero:\n",
    "                    continue\n",
    "                buf[idx]=c\n",
    "                dfs(buf)\n",
    "                buf[idx]='.'\n",
    "        ans=[]\n",
    "        buf=['.']*(len(num)*2-1)\n",
    "        for i in range(len(num)):\n",
    "            buf[2*i]=num[i]\n",
    "        # print(buf)\n",
    "        dfs(buf)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        def calc(s):\n",
    "            opt=[]\n",
    "            exp=[]\n",
    "            num=0\n",
    "            last_is_digit=False\n",
    "            for ch in s:\n",
    "                if ch.isdigit():\n",
    "                    last_is_digit=True\n",
    "                    num=num*10+int(ch)\n",
    "                else:\n",
    "                    if last_is_digit:\n",
    "                        last_is_digit=False\n",
    "                        exp.append(num)\n",
    "                        num=0\n",
    "                    if ch=='*':\n",
    "                        opt.append(ch)\n",
    "                    else:\n",
    "                        while opt and (opt[-1]=='*' or opt[-1]=='-'):\n",
    "                            exp.append(opt.pop())\n",
    "                        opt.append(ch)\n",
    "            if last_is_digit:\n",
    "                exp.append(num)\n",
    "            while opt:\n",
    "                exp.append(opt.pop())\n",
    "            ans=0\n",
    "            st=[]\n",
    "            # print(exp)\n",
    "            for e in exp:\n",
    "                if isinstance(e,int):\n",
    "                    st.append(e)\n",
    "                else:\n",
    "                    b=st.pop()\n",
    "                    a=st.pop()\n",
    "                    if e=='-':\n",
    "                        r=a-b\n",
    "                    elif e=='+':\n",
    "                        r=a+b\n",
    "                    else:\n",
    "                        r=a*b\n",
    "                    st.append(r)\n",
    "            assert len(st)==1\n",
    "            return st[0]\n",
    "        # print(calc('1+2*3'))\n",
    "        # print(calc('3*4*5-6-2*3'))\n",
    "        # print(calc('3-4-56+2+3'))\n",
    "        def dfs(buf):\n",
    "            if '.' not in buf:\n",
    "                e=''.join(buf)\n",
    "                if calc(e)==target:\n",
    "                    ans.append(e)\n",
    "                return\n",
    "            idx=buf.index('.')\n",
    "            # print(buf,idx)\n",
    "            pre_is_zero= True if buf[idx-1]=='0' and (idx==1 or buf[idx-2]!='') else False\n",
    "            for c in ['*','','+','-',]:\n",
    "                if c=='' and pre_is_zero:\n",
    "                    continue\n",
    "                buf[idx]=c\n",
    "                dfs(buf)\n",
    "                buf[idx]='.'\n",
    "        ans=[]\n",
    "        buf=['.']*(len(num)*2-1)\n",
    "        for i in range(len(num)):\n",
    "            buf[2*i]=num[i]\n",
    "        # print(buf)\n",
    "        dfs(buf)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        ops = [\"*\", \"+\", \"\", \"-\"]\n",
    "        def dfs(idx, sign, curv, val, path):\n",
    "            c = num[idx]\n",
    "            curv = 10 * curv + int(c)\n",
    "            if idx == n - 1:\n",
    "                if sign * curv + val == target:\n",
    "                    path.append(num[idx])\n",
    "                    ans.append(\"\".join(path))\n",
    "                    path.pop()\n",
    "                return\n",
    "            for i in (-1, 0, 1, 2):\n",
    "                path.append(num[idx] + ops[i])\n",
    "                if not i:\n",
    "                    dfs(idx + 1, sign * curv, 0, val, path)\n",
    "                elif i < 2:\n",
    "                    dfs(idx + 1, i, 0, val + sign * curv, path)\n",
    "                elif curv or c != '0':\n",
    "                    dfs(idx + 1, sign, curv, val, path)\n",
    "                path.pop()\n",
    "\n",
    "        ans = []\n",
    "        n = len(num)\n",
    "        dfs(0, 1, 0, 0, [])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        def calc(s):\n",
    "            opt=[]\n",
    "            exp=[]\n",
    "            num=0\n",
    "            last_is_digit=False\n",
    "            for ch in s:\n",
    "                if ch.isdigit():\n",
    "                    last_is_digit=True\n",
    "                    num=num*10+int(ch)\n",
    "                else:\n",
    "                    if last_is_digit:\n",
    "                        last_is_digit=False\n",
    "                        exp.append(num)\n",
    "                        num=0\n",
    "                    if ch=='*':\n",
    "                        opt.append(ch)\n",
    "                    else:\n",
    "                        while opt and (opt[-1]=='*' or opt[-1]=='-'):\n",
    "                            exp.append(opt.pop())\n",
    "                        opt.append(ch)\n",
    "            if last_is_digit:\n",
    "                exp.append(num)\n",
    "            while opt:\n",
    "                exp.append(opt.pop())\n",
    "            ans=0\n",
    "            st=[]\n",
    "            # print(exp)\n",
    "            for e in exp:\n",
    "                if isinstance(e,int):\n",
    "                    st.append(e)\n",
    "                else:\n",
    "                    b=st.pop()\n",
    "                    a=st.pop()\n",
    "                    if e=='-':\n",
    "                        r=a-b\n",
    "                    elif e=='+':\n",
    "                        r=a+b\n",
    "                    else:\n",
    "                        r=a*b\n",
    "                    st.append(r)\n",
    "            assert len(st)==1\n",
    "            return st[0]\n",
    "        def dfs(buf):\n",
    "            if '.' not in buf:\n",
    "                e=''.join(buf)\n",
    "                if calc(e)==target:\n",
    "                    ans.append(e)\n",
    "                return\n",
    "            idx=buf.index('.')\n",
    "            pre_is_zero= buf[idx-1]=='0' and (idx==1 or buf[idx-2]!='')\n",
    "            for c in ['*','','+','-',]:\n",
    "                if c=='' and pre_is_zero:\n",
    "                    continue\n",
    "                buf[idx]=c\n",
    "                dfs(buf)\n",
    "                buf[idx]='.'\n",
    "        ans=[]\n",
    "        buf=['.']*(len(num)*2-1)\n",
    "        for i in range(len(num)):\n",
    "            buf[2*i]=num[i]\n",
    "        dfs(buf)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "        ans = []\n",
    "        def dfs(i, exp, res, mul):\n",
    "            if i == n:\n",
    "                if res == target:\n",
    "                    ans.append(''.join(exp))\n",
    "                return\n",
    "\n",
    "            val = 0\n",
    "            # 枚举拆分位置\n",
    "            for j in range(i, n):\n",
    "                #[i,j]位置上是这次拆出来的数字，不能有前导0\n",
    "                if j > i and num[i] == '0':\n",
    "                    break\n",
    "                val = val * 10 + int(num[j])\n",
    "                if i == 0:\n",
    "                    exp.append(str(val))\n",
    "                    dfs(j + 1, exp, val, val)\n",
    "                    exp.pop()\n",
    "                else:\n",
    "                    exp.append('+')\n",
    "                    exp.append(str(val))\n",
    "                    dfs(j + 1, exp, res + val, val)\n",
    "                    exp.pop()\n",
    "                    exp.pop()\n",
    "\n",
    "                    exp.append('-')\n",
    "                    exp.append(str(val))\n",
    "                    dfs(j + 1, exp, res - val, -val)\n",
    "                    exp.pop()\n",
    "                    exp.pop()\n",
    "\n",
    "                    exp.append('*')\n",
    "                    exp.append(str(val))\n",
    "                    dfs(j + 1, exp, res - mul + mul * val, mul * val)\n",
    "                    exp.pop()\n",
    "                    exp.pop()\n",
    "\n",
    "        dfs(0, [], 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        res_list = []\n",
    "        def backtrace(i, tmp_value, last_num, sum_value, expression, note):\n",
    "            if i == len(num):\n",
    "                if sum_value + tmp_value == target:\n",
    "                    res_list.append((expression, note))\n",
    "                return\n",
    "            cur_value = int(num[i])\n",
    "            # concate\n",
    "            if last_num != 0:\n",
    "                last_num_ = last_num * 10 + cur_value\n",
    "                tmp_value_ = tmp_value / last_num * last_num_\n",
    "                backtrace(i+1, tmp_value_, last_num_, sum_value, expression + num[i], note+f'tmp:{tmp_value_} sum:{sum_value}\\n')\n",
    "            # add\n",
    "            backtrace(i+1, cur_value, cur_value, sum_value + tmp_value, expression + '+' + num[i], note+f'tmp:{cur_value} sum:{sum_value+tmp_value}\\n')\n",
    "            # sub\n",
    "            backtrace(i+1, -cur_value, cur_value, sum_value + tmp_value, expression + '-' + num[i], note+f'tmp:{-cur_value} sum:{sum_value + tmp_value}\\n')\n",
    "            # multiple\n",
    "            backtrace(i+1, tmp_value * cur_value, cur_value, sum_value, expression + '*' + num[i], note+f'tmp:{tmp_value * cur_value} sum:{sum_value}\\n')\n",
    "            return\n",
    "        backtrace(1, int(num[0]), int(num[0]), 0, num[0], '')\n",
    "        res = []\n",
    "        for e in res_list:\n",
    "            res.append(e[0])\n",
    "            print(e[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef addOperators(self, num: str, target: int) -> List[str]:\n",
    "\t\tn = len(num)\n",
    "\t\tans = []\n",
    "\t\tqueue = deque([(0, '', 0, 0)]) # start index, string so far, value, previous added\n",
    "\n",
    "\t\twhile queue:\n",
    "\t\t\tstart, prefix, value, prev = queue.popleft()\n",
    "\t\t\tif start == n: # 问所有解，无法提前终止，出队检查\n",
    "\t\t\t\tif value == target:\n",
    "\t\t\t\t\tans.append(prefix)\n",
    "\t\t\t\tcontinue # 可以不写，后面的范围是空，不会进入循环\n",
    "\t\t\tfor end in range(start, n):\n",
    "\t\t\t\tstring = num[start:end + 1]\n",
    "\t\t\t\tnumber = int(string)\n",
    "\t\t\t\tif end > start and num[start] == '0': break # 不能以 0 开头 , 后面不用再试了\n",
    "\t\t\t\tif start == 0:\n",
    "\t\t\t\t\tqueue.append((end + 1, string, number, number))\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tif int(num[start:]) >= abs(target - value):\n",
    "\t\t\t\t\t\tqueue.append((end + 1, prefix + '+' + string, value + number, number))\n",
    "\t\t\t\t\t\tqueue.append((end + 1, prefix + '-' + string, value - number, -number))\n",
    "\t\t\t\t\tqueue.append((end + 1, prefix + '*' + string, value - prev + prev * number, prev * number))\n",
    "\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addOperators(self, num: str, target: int) -> List[str]:\n",
    "        n = len(num)\n",
    "\n",
    "        def judge(formula: str, idx: List[int]) -> bool:\n",
    "            if not formula:\n",
    "                if num[0] == \"0\":\n",
    "                    return False\n",
    "                else:\n",
    "                    return int(num) == target\n",
    "            st = deque()\n",
    "            t_idx = idx + [n]\n",
    "            t = num[t_idx[0] : t_idx[1]]\n",
    "            if t_idx[1] - t_idx[0] > 1 and t[0] == \"0\":\n",
    "                return False\n",
    "            st.append(int(t))\n",
    "            for i, ops in enumerate(formula):\n",
    "                l = int(t_idx[i + 1])\n",
    "                r = int(t_idx[i + 2])\n",
    "                t = num[l:r]\n",
    "                if r - l > 1 and t[0] == \"0\":\n",
    "                    return False\n",
    "                if ops == \"+\":\n",
    "                    st.append(int(t))\n",
    "                elif ops == \"-\":\n",
    "                    st.append(-int(t))\n",
    "                else:\n",
    "                    a = st.pop()\n",
    "                    st.append(a * int(t))\n",
    "            return sum(st) == target\n",
    "    \n",
    "        ret = []\n",
    "        if judge(\"\", [0]):\n",
    "            ret.append(num)\n",
    "        if n == 1:\n",
    "            return ret\n",
    "\n",
    "        que = deque([(\"\", [0], 1)])\n",
    "        while que:\n",
    "            formula, idx, step = que.popleft()\n",
    "            for opr in [\"+\", \"-\", \"*\"]:\n",
    "                tf = formula + opr\n",
    "                tidx = idx + [step]\n",
    "                if judge(tf, tidx):\n",
    "                    tt = \"\"\n",
    "                    for ii in range(len(tidx)-1):\n",
    "                        tt += num[tidx[ii] : tidx[ii+1]]\n",
    "                        tt += tf[ii]\n",
    "                    tt += num[tidx[-1]:]\n",
    "                    ret.append(tt)\n",
    "                if step >= n - 1:\n",
    "                    continue\n",
    "                que.append((tf, tidx, step + 1))\n",
    "            if step >= n - 1:\n",
    "                continue\n",
    "            que.append((formula, idx, step + 1))\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
